home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer)…68k, x86, SPARC, PA-RISC] / NeXTSTEP 3.3 Dev Intel.iso / NextDeveloper / Headers / g++ / gen / AVLSet.ccP < prev    next >
Text File  |  1995-02-06  |  18KB  |  894 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <stream.h>
  23. #include "<T>.AVLSet.h"
  24. extern "C" {
  25. #include <stdlib.h>
  26. }
  27.  
  28. /*
  29.  constants & inlines for maintaining balance & thread status in tree nodes
  30. */
  31.  
  32. #define AVLBALANCEMASK    3
  33. #define AVLBALANCED       0
  34. #define AVLLEFTHEAVY      1
  35. #define AVLRIGHTHEAVY     2
  36.  
  37. #define LTHREADBIT        4
  38. #define RTHREADBIT        8
  39.  
  40.  
  41. static inline int bf(<T>AVLNode* t)
  42. {
  43.   return t->stat & AVLBALANCEMASK;
  44. }
  45.  
  46. static inline void set_bf(<T>AVLNode* t, int b)
  47. {
  48.   t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
  49. }
  50.  
  51.  
  52. static inline int rthread(<T>AVLNode* t)
  53. {
  54.   return t->stat & RTHREADBIT;
  55. }
  56.  
  57. static inline void set_rthread(<T>AVLNode* t, int b)
  58. {
  59.   if (b)
  60.     t->stat |= RTHREADBIT;
  61.   else
  62.     t->stat &= ~RTHREADBIT;
  63. }
  64.  
  65. static inline int lthread(<T>AVLNode* t)
  66. {
  67.   return t->stat & LTHREADBIT;
  68. }
  69.  
  70. static inline void set_lthread(<T>AVLNode* t, int b)
  71. {
  72.   if (b)
  73.     t->stat |= LTHREADBIT;
  74.   else
  75.     t->stat &= ~LTHREADBIT;
  76. }
  77.  
  78. /*
  79.  traversal primitives
  80. */
  81.  
  82.  
  83. <T>AVLNode* <T>AVLSet::leftmost()
  84. {
  85.   <T>AVLNode* t = root;
  86.   if (t != 0) while (t->lt != 0) t = t->lt;
  87.   return t;
  88. }
  89.  
  90. <T>AVLNode* <T>AVLSet::rightmost()
  91. {
  92.   <T>AVLNode* t = root;
  93.   if (t != 0) while (t->rt != 0) t = t->rt;
  94.   return t;
  95. }
  96.  
  97. <T>AVLNode* <T>AVLSet::succ(<T>AVLNode* t)
  98. {
  99.   <T>AVLNode* r = t->rt;
  100.   if (!rthread(t)) while (!lthread(r)) r = r->lt;
  101.   return r;
  102. }
  103.  
  104. <T>AVLNode* <T>AVLSet::pred(<T>AVLNode* t)
  105. {
  106.   <T>AVLNode* l = t->lt;
  107.   if (!lthread(t)) while (!rthread(l)) l = l->rt;
  108.   return l;
  109. }
  110.  
  111.  
  112. Pix <T>AVLSet::seek(<T&> key)
  113. {
  114.   <T>AVLNode* t = root;
  115.   if (t == 0)
  116.     return 0;
  117.   for (;;)
  118.   {
  119.     int cmp = <T>CMP(key, t->item);
  120.     if (cmp == 0)
  121.       return Pix(t);
  122.     else if (cmp < 0)
  123.     {
  124.       if (lthread(t))
  125.         return 0;
  126.       else
  127.         t = t->lt;
  128.     }
  129.     else if (rthread(t))
  130.       return 0;
  131.     else
  132.       t = t->rt;
  133.   }
  134. }
  135.  
  136.  
  137. /*
  138.  The combination of threads and AVL bits make adding & deleting
  139.  interesting, but very awkward.
  140.  
  141.  We use the following statics to avoid passing them around recursively
  142. */
  143.  
  144. static int _need_rebalancing;   // to send back balance info from rec. calls
  145. static <T>*   _target_item;     // add/del_item target
  146. static <T>AVLNode* _found_node; // returned added/deleted node
  147. static int    _already_found;   // for deletion subcases
  148.  
  149. static <T>AVLNode** _hold_nodes;       // used for rebuilding trees
  150. static int  _max_hold_index;              // # elements-1 in _hold_nodes
  151.  
  152.  
  153. void <T>AVLSet:: _add(<T>AVLNode*& t)
  154. {
  155.   int cmp = <T>CMP(*_target_item, t->item);
  156.   if (cmp == 0)
  157.   {
  158.     _found_node = t;
  159.     return;
  160.   }
  161.   else if (cmp < 0)
  162.   {
  163.     if (lthread(t))
  164.     {
  165.       ++count;
  166.       _found_node = new <T>AVLNode(*_target_item);
  167.       set_lthread(_found_node, 1);
  168.       set_rthread(_found_node, 1);
  169.       _found_node->lt = t->lt;
  170.       _found_node->rt = t;
  171.       t->lt = _found_node;
  172.       set_lthread(t, 0);
  173.       _need_rebalancing = 1;
  174.     }
  175.     else
  176.       _add(t->lt);
  177.     if (_need_rebalancing)
  178.     {
  179.       switch(bf(t))
  180.       {
  181.       case AVLRIGHTHEAVY:
  182.         set_bf(t, AVLBALANCED);
  183.         _need_rebalancing = 0;
  184.         return;
  185.       case AVLBALANCED:
  186.         set_bf(t, AVLLEFTHEAVY);
  187.         return;
  188.       case AVLLEFTHEAVY:
  189.     {
  190.         <T>AVLNode* l = t->lt;
  191.         if (bf(l) == AVLLEFTHEAVY)
  192.         {
  193.           if (rthread(l))
  194.             t->lt = l;
  195.           else
  196.             t->lt = l->rt;
  197.           set_lthread(t, rthread(l));
  198.           l->rt = t;
  199.           set_rthread(l, 0);
  200.           set_bf(t, AVLBALANCED);
  201.           set_bf(l, AVLBALANCED);
  202.           t = l;
  203.           _need_rebalancing = 0;
  204.         }
  205.         else
  206.         {
  207.           <T>AVLNode* r = l->rt;
  208.           set_rthread(l, lthread(r));
  209.           if (lthread(r))
  210.             l->rt = r;
  211.           else
  212.             l->rt = r->lt;
  213.           r->lt = l;
  214.           set_lthread(r, 0);
  215.           set_lthread(t, rthread(r));
  216.           if (rthread(r))
  217.             t->lt = r;
  218.           else
  219.             t->lt = r->rt;
  220.           r->rt = t;
  221.           set_rthread(r, 0);
  222.           if (bf(r) == AVLLEFTHEAVY)
  223.             set_bf(t, AVLRIGHTHEAVY);
  224.           else
  225.             set_bf(t, AVLBALANCED);
  226.           if (bf(r) == AVLRIGHTHEAVY)
  227.             set_bf(l, AVLLEFTHEAVY);
  228.           else
  229.             set_bf(l, AVLBALANCED);
  230.           set_bf(r, AVLBALANCED);
  231.           t = r;
  232.           _need_rebalancing = 0;
  233.           return;
  234.         }
  235.     }
  236.       }
  237.     }
  238.   }
  239.   else
  240.   {
  241.     if (rthread(t))
  242.     {
  243.       ++count;
  244.       _found_node = new <T>AVLNode(*_target_item);
  245.       set_rthread(t, 0);
  246.       set_lthread(_found_node, 1);
  247.       set_rthread(_found_node, 1);
  248.       _found_node->lt = t;
  249.       _found_node->rt = t->rt;
  250.       t->rt = _found_node;
  251.       _need_rebalancing = 1;
  252.     }
  253.     else
  254.       _add(t->rt);
  255.     if (_need_rebalancing)
  256.     {
  257.       switch(bf(t))
  258.       {
  259.       case AVLLEFTHEAVY:
  260.         set_bf(t, AVLBALANCED);
  261.         _need_rebalancing = 0;
  262.         return;
  263.       case AVLBALANCED:
  264.         set_bf(t, AVLRIGHTHEAVY);
  265.         return;
  266.       case AVLRIGHTHEAVY:
  267.     {
  268.         <T>AVLNode* r = t->rt;
  269.         if (bf(r) == AVLRIGHTHEAVY)
  270.         {
  271.           if (lthread(r))
  272.             t->rt = r;
  273.           else
  274.             t->rt = r->lt;
  275.           set_rthread(t, lthread(r));
  276.           r->lt = t;
  277.           set_lthread(r, 0);
  278.           set_bf(t, AVLBALANCED);
  279.           set_bf(r, AVLBALANCED);
  280.           t = r;
  281.           _need_rebalancing = 0;
  282.         }
  283.         else
  284.         {
  285.           <T>AVLNode* l = r->lt;
  286.           set_lthread(r, rthread(l));
  287.           if (rthread(l))
  288.             r->lt = l;
  289.           else
  290.             r->lt = l->rt;
  291.           l->rt = r;
  292.           set_rthread(l, 0);
  293.           set_rthread(t, lthread(l));
  294.           if (lthread(l))
  295.             t->rt = l;
  296.           else
  297.             t->rt = l->lt;
  298.           l->lt = t;
  299.           set_lthread(l, 0);
  300.           if (bf(l) == AVLRIGHTHEAVY)
  301.             set_bf(t, AVLLEFTHEAVY);
  302.           else
  303.             set_bf(t, AVLBALANCED);
  304.           if (bf(l) == AVLLEFTHEAVY)
  305.             set_bf(r, AVLRIGHTHEAVY);
  306.           else
  307.             set_bf(r, AVLBALANCED);
  308.           set_bf(l, AVLBALANCED);
  309.           t = l;
  310.           _need_rebalancing = 0;
  311.           return;
  312.         }
  313.     }
  314.       }
  315.     }
  316.   }
  317. }
  318.  
  319.     
  320. Pix <T>AVLSet::add(<T&> item)
  321. {
  322.   if (root == 0)
  323.   {
  324.     ++count;
  325.     root = new <T>AVLNode(item);
  326.     set_rthread(root, 1);
  327.     set_lthread(root, 1);
  328.     return Pix(root);
  329.   }
  330.   else
  331.   {
  332.     _target_item = &item;
  333.     _need_rebalancing = 0;
  334.     _add(root);
  335.     return Pix(_found_node);
  336.   }
  337. }
  338.  
  339.  
  340. void <T>AVLSet::_del(<T>AVLNode* par, <T>AVLNode*& t)
  341. {
  342.   int comp;
  343.   if (_already_found)
  344.   {
  345.     if (rthread(t))
  346.       comp = 0;
  347.     else
  348.       comp = 1;
  349.   }
  350.   else 
  351.     comp = <T>CMP(*_target_item, t->item);
  352.   if (comp == 0)
  353.   {
  354.     if (lthread(t) && rthread(t))
  355.     {
  356.       _found_node = t;
  357.       if (t == par->lt)
  358.       {
  359.         set_lthread(par, 1);
  360.         par->lt = t->lt;
  361.       }
  362.       else
  363.       {
  364.         set_rthread(par, 1);
  365.         par->rt = t->rt;
  366.       }
  367.       _need_rebalancing = 1;
  368.       return;
  369.     }
  370.     else if (lthread(t))
  371.     {
  372.       _found_node = t;
  373.       <T>AVLNode* s = succ(t);
  374.       if (s != 0 && lthread(s))
  375.         s->lt = t->lt;
  376.       t = t->rt;
  377.       _need_rebalancing = 1;
  378.       return;
  379.     }
  380.     else if (rthread(t))
  381.     {
  382.       _found_node = t;
  383.       <T>AVLNode* p = pred(t);
  384.       if (p != 0 && rthread(p))
  385.         p->rt = t->rt;
  386.       t = t->lt;
  387.       _need_rebalancing = 1;
  388.       return;
  389.     }
  390.     else                        // replace item & find someone deletable
  391.     {
  392.       <T>AVLNode* p = pred(t);
  393.       t->item = p->item;
  394.       _already_found = 1;
  395.       comp = -1;                // fall through below to left
  396.     }
  397.   }
  398.  
  399.   if (comp < 0)
  400.   {
  401.     if (lthread(t))
  402.       return;
  403.     _del(t, t->lt);
  404.     if (!_need_rebalancing)
  405.       return;
  406.     switch (bf(t))
  407.     {
  408.     case AVLLEFTHEAVY:
  409.       set_bf(t, AVLBALANCED);
  410.       return;
  411.     case AVLBALANCED:
  412.       set_bf(t, AVLRIGHTHEAVY);
  413.       _need_rebalancing = 0;
  414.       return;
  415.     case AVLRIGHTHEAVY:
  416.       {
  417.       <T>AVLNode* r = t->rt;
  418.       switch (bf(r))
  419.       {
  420.       case AVLBALANCED:
  421.         if (lthread(r))
  422.           t->rt = r;
  423.         else
  424.           t->rt = r->lt;
  425.         set_rthread(t, lthread(r));
  426.         r->lt = t;
  427.         set_lthread(r, 0);
  428.         set_bf(t, AVLRIGHTHEAVY);
  429.         set_bf(r, AVLLEFTHEAVY);
  430.         _need_rebalancing = 0;
  431.         t = r;
  432.         return;
  433.       case AVLRIGHTHEAVY:
  434.         if (lthread(r))
  435.           t->rt = r;
  436.         else
  437.           t->rt = r->lt;
  438.         set_rthread(t, lthread(r));
  439.         r->lt = t;
  440.         set_lthread(r, 0);
  441.         set_bf(t, AVLBALANCED);
  442.         set_bf(r, AVLBALANCED);
  443.         t = r;
  444.         return;
  445.       case AVLLEFTHEAVY:
  446.     {
  447.         <T>AVLNode* l = r->lt;
  448.         set_lthread(r, rthread(l));
  449.         if (rthread(l))
  450.           r->lt = l;
  451.         else
  452.           r->lt = l->rt;
  453.         l->rt = r;
  454.         set_rthread(l, 0);
  455.         set_rthread(t, lthread(l));
  456.         if (lthread(l))
  457.           t->rt = l;
  458.         else
  459.           t->rt = l->lt;
  460.         l->lt = t;
  461.         set_lthread(l, 0);
  462.         if (bf(l) == AVLRIGHTHEAVY)
  463.           set_bf(t, AVLLEFTHEAVY);
  464.         else
  465.           set_bf(t, AVLBALANCED);
  466.         if (bf(l) == AVLLEFTHEAVY)
  467.           set_bf(r, AVLRIGHTHEAVY);
  468.         else
  469.           set_bf(r, AVLBALANCED);
  470.         set_bf(l, AVLBALANCED);
  471.         t = l;
  472.         return;
  473.     }
  474.       }
  475.     }
  476.     }
  477.   }
  478.   else
  479.   {
  480.     if (rthread(t))
  481.       return;
  482.     _del(t, t->rt);
  483.     if (!_need_rebalancing)
  484.       return;
  485.     switch (bf(t))
  486.     {
  487.     case AVLRIGHTHEAVY:
  488.       set_bf(t, AVLBALANCED);
  489.       return;
  490.     case AVLBALANCED:
  491.       set_bf(t, AVLLEFTHEAVY);
  492.       _need_rebalancing = 0;
  493.       return;
  494.     case AVLLEFTHEAVY:
  495.       {
  496.       <T>AVLNode* l = t->lt;
  497.       switch (bf(l))
  498.       {
  499.       case AVLBALANCED:
  500.         if (rthread(l))
  501.           t->lt = l;
  502.         else
  503.           t->lt = l->rt;
  504.         set_lthread(t, rthread(l));
  505.         l->rt = t;
  506.         set_rthread(l, 0);
  507.         set_bf(t, AVLLEFTHEAVY);
  508.         set_bf(l, AVLRIGHTHEAVY);
  509.         _need_rebalancing = 0;
  510.         t = l;
  511.         return;
  512.       case AVLLEFTHEAVY:
  513.         if (rthread(l))
  514.           t->lt = l;
  515.         else
  516.           t->lt = l->rt;
  517.         set_lthread(t, rthread(l));
  518.         l->rt = t;
  519.         set_rthread(l, 0);
  520.         set_bf(t, AVLBALANCED);
  521.         set_bf(l, AVLBALANCED);
  522.         t = l;
  523.         return;
  524.       case AVLRIGHTHEAVY:
  525.     {
  526.         <T>AVLNode* r = l->rt;
  527.         set_rthread(l, lthread(r));
  528.         if (lthread(r))
  529.           l->rt = r;
  530.         else
  531.           l->rt = r->lt;
  532.         r->lt = l;
  533.         set_lthread(r, 0);
  534.         set_lthread(t, rthread(r));
  535.         if (rthread(r))
  536.           t->lt = r;
  537.         else
  538.           t->lt = r->rt;
  539.         r->rt = t;
  540.         set_rthread(r, 0);
  541.         if (bf(r) == AVLLEFTHEAVY)
  542.           set_bf(t, AVLRIGHTHEAVY);
  543.         else
  544.           set_bf(t, AVLBALANCED);
  545.         if (bf(r) == AVLRIGHTHEAVY)
  546.           set_bf(l, AVLLEFTHEAVY);
  547.         else
  548.           set_bf(l, AVLBALANCED);
  549.         set_bf(r, AVLBALANCED);
  550.         t = r;
  551.         return;
  552.     }
  553.       }
  554.       }
  555.     }
  556.   }
  557. }
  558.  
  559.         
  560.  
  561. void <T>AVLSet::del(<T&> item)
  562. {
  563.   if (root == 0) return;
  564.   _need_rebalancing = 0;
  565.   _already_found = 0;
  566.   _found_node = 0;
  567.   _target_item = &item;
  568.   _del(root, root);
  569.   if (_found_node)
  570.   {
  571.     delete(_found_node);
  572.     if (--count == 0)
  573.       root = 0;
  574.   }
  575. }
  576.  
  577. // build an ordered array of pointers to tree nodes back into a tree
  578. // we know that at least one element exists
  579.  
  580. static <T>AVLNode* _do_treeify(int lo, int hi, int& h)
  581. {
  582.   int lh, rh;
  583.   int mid = (lo + hi) / 2;
  584.   <T>AVLNode* t = _hold_nodes[mid];
  585.   if (lo > mid - 1)
  586.   {
  587.     set_lthread(t, 1);
  588.     if (mid == 0)
  589.       t->lt = 0;
  590.     else
  591.       t->lt = _hold_nodes[mid-1];
  592.     lh = 0;
  593.   }
  594.   else
  595.   {
  596.     set_lthread(t, 0);
  597.     t->lt = _do_treeify(lo, mid-1, lh);
  598.   }
  599.   if (hi < mid + 1)
  600.   {
  601.     set_rthread(t, 1);
  602.     if (mid == _max_hold_index)
  603.       t->rt = 0;
  604.     else
  605.       t->rt = _hold_nodes[mid+1];
  606.     rh = 0;
  607.   }
  608.   else 
  609.   {
  610.     set_rthread(t, 0);
  611.     t->rt = _do_treeify(mid+1, hi, rh);
  612.   }
  613.   if (lh == rh)
  614.   {
  615.     set_bf(t, AVLBALANCED);
  616.     h = lh + 1;
  617.   }
  618.   else if (lh == rh - 1)
  619.   {
  620.     set_bf(t, AVLRIGHTHEAVY);
  621.     h = rh + 1;
  622.   }
  623.   else if (rh == lh - 1)
  624.   {
  625.     set_bf(t, AVLLEFTHEAVY);
  626.     h = lh + 1;
  627.   }
  628.   else                          // can't happen
  629.     abort();
  630.  
  631.   return t;
  632. }
  633.  
  634. static <T>AVLNode* _treeify(int n)
  635. {
  636.   <T>AVLNode* t;
  637.   if (n == 0)
  638.     t = 0;
  639.   else
  640.   {
  641.     int b;
  642.     _max_hold_index = n-1;
  643.     t = _do_treeify(0, _max_hold_index, b);
  644.   }
  645.   delete _hold_nodes;
  646.   return t;
  647. }
  648.  
  649.  
  650. void <T>AVLSet::_kill(<T>AVLNode* t)
  651. {
  652.   if (t != 0)
  653.   {
  654.     if (!lthread(t)) _kill(t->lt);
  655.     if (!rthread(t)) _kill(t->rt);
  656.     delete t;
  657.   }
  658. }
  659.  
  660.  
  661. <T>AVLSet::<T>AVLSet(<T>AVLSet& b)
  662. {
  663.   if ((count = b.count) == 0)
  664.   {
  665.     root = 0;
  666.   }
  667.   else
  668.   {
  669.     _hold_nodes = new <T>AVLNodePtr [count];
  670.     <T>AVLNode* t = b.leftmost();
  671.     int i = 0;
  672.     while (t != 0)
  673.     {
  674.       _hold_nodes[i++] = new <T>AVLNode(t->item);
  675.       t = b.succ(t);
  676.     }
  677.     root = _treeify(count);
  678.   }
  679. }
  680.  
  681.  
  682. int <T>AVLSet::operator == (<T>AVLSet& y)
  683. {
  684.   if (count != y.count)
  685.     return 0;
  686.   else
  687.   {
  688.     <T>AVLNode* t = leftmost();
  689.     <T>AVLNode* u = y.leftmost();
  690.     for (;;)
  691.     {
  692.       if (t == 0)
  693.         return 1;
  694.       else if (!(<T>EQ(t->item, u->item)))
  695.         return 0;
  696.       else
  697.       {
  698.         t = succ(t);
  699.         u = y.succ(u);
  700.       }
  701.     }
  702.   }
  703. }
  704.  
  705. int <T>AVLSet::operator <= (<T>AVLSet& y)
  706. {
  707.   if (count > y.count)
  708.     return 0;
  709.   else
  710.   {
  711.     <T>AVLNode* t = leftmost();
  712.     <T>AVLNode* u = y.leftmost();
  713.     for (;;)
  714.     {
  715.       if (t == 0)
  716.         return 1;
  717.       else if (u == 0)
  718.         return 0;
  719.       int cmp = <T>CMP(t->item, u->item);
  720.       if (cmp == 0)
  721.       {
  722.         t = succ(t);
  723.         u = y.succ(u);
  724.       }
  725.       else if (cmp < 0)
  726.         return 0;
  727.       else
  728.         u = y.succ(u);
  729.     }
  730.   }
  731. }
  732.  
  733. void <T>AVLSet::operator |=(<T>AVLSet& y)
  734. {
  735.   <T>AVLNode* t = leftmost();
  736.   <T>AVLNode* u = y.leftmost();
  737.   int rsize = count + y.count;
  738.   _hold_nodes = new <T>AVLNodePtr [rsize];
  739.   int k = 0;
  740.   for (;;)
  741.   {
  742.     if (t == 0)
  743.     {
  744.       while (u != 0)
  745.       {
  746.         _hold_nodes[k++] = new <T>AVLNode(u->item);
  747.         u = y.succ(u);
  748.       }
  749.       break;
  750.     }
  751.     else if (u == 0)
  752.     {
  753.       while (t != 0)
  754.       {
  755.         _hold_nodes[k++] = t;
  756.         t = succ(t);
  757.       }
  758.       break;
  759.     }
  760.     int cmp = <T>CMP(t->item, u->item);
  761.     if (cmp == 0)
  762.     {
  763.       _hold_nodes[k++] = t;
  764.       t = succ(t);
  765.       u = y.succ(u);
  766.     }
  767.     else if (cmp < 0)
  768.     {
  769.       _hold_nodes[k++] = t;
  770.       t = succ(t);
  771.     }
  772.     else
  773.     {
  774.       _hold_nodes[k++] = new <T>AVLNode(u->item);
  775.       u = y.succ(u);
  776.     }
  777.   }
  778.   root = _treeify(k);
  779.   count = k;
  780. }
  781.  
  782. void <T>AVLSet::operator &= (<T>AVLSet& y)
  783. {
  784.   <T>AVLNode* t = leftmost();
  785.   <T>AVLNode* u = y.leftmost();
  786.   int rsize = (count < y.count)? count : y.count;
  787.   _hold_nodes = new <T>AVLNodePtr [rsize];
  788.   int k = 0;
  789.   for (;;)
  790.   {
  791.     if (t == 0)
  792.       break;
  793.     if (u == 0)
  794.     {
  795.       while (t != 0)
  796.       {
  797.         <T>AVLNode* tmp = succ(t);
  798.         delete t;
  799.         t = tmp;
  800.       }
  801.       break;
  802.     }
  803.     int cmp = <T>CMP(t->item, u->item);
  804.     if (cmp == 0)
  805.     {
  806.       _hold_nodes[k++] = t;
  807.       t = succ(t);
  808.       u = y.succ(u);
  809.     }
  810.     else if (cmp < 0)
  811.     {
  812.       <T>AVLNode* tmp = succ(t);
  813.       delete t;
  814.       t = tmp;
  815.     }
  816.     else
  817.       u = y.succ(u);
  818.   }
  819.   root = _treeify(k);
  820.   count = k;
  821. }
  822.  
  823.  
  824. void <T>AVLSet::operator -=(<T>AVLSet& y)
  825. {
  826.   <T>AVLNode* t = leftmost();
  827.   <T>AVLNode* u = y.leftmost();
  828.   int rsize = count;
  829.   _hold_nodes = new <T>AVLNodePtr [rsize];
  830.   int k = 0;
  831.   for (;;)
  832.   {
  833.     if (t == 0)
  834.       break;
  835.     else if (u == 0)
  836.     {
  837.       while (t != 0)
  838.       {
  839.         _hold_nodes[k++] = t;
  840.         t = succ(t);
  841.       }
  842.       break;
  843.     }
  844.     int cmp = <T>CMP(t->item, u->item);
  845.     if (cmp == 0)
  846.     {
  847.       <T>AVLNode* tmp = succ(t);
  848.       delete t;
  849.       t = tmp;
  850.       u = y.succ(u);
  851.     }
  852.     else if (cmp < 0)
  853.     {
  854.       _hold_nodes[k++] = t;
  855.       t = succ(t);
  856.     }
  857.     else
  858.       u = y.succ(u);
  859.   }
  860.   root = _treeify(k);
  861.   count = k;
  862. }
  863.  
  864. int <T>AVLSet::owns(Pix i)
  865. {
  866.   if (i == 0) return 0;
  867.   for (<T>AVLNode* t = leftmost(); t != 0; t = succ(t)) 
  868.     if (Pix(t) == i) return 1;
  869.   return 0;
  870. }
  871.  
  872. int <T>AVLSet::OK()
  873. {
  874.   int v = 1;
  875.   if (root == 0) 
  876.     v = count == 0;
  877.   else
  878.   {
  879.     int n = 1;
  880.     <T>AVLNode* trail = leftmost();
  881.     <T>AVLNode* t = succ(trail);
  882.     while (t != 0)
  883.     {
  884.       ++n;
  885.       v &= <T>CMP(trail->item, t->item) < 0;
  886.       trail = t;
  887.       t = succ(t);
  888.     }
  889.     v &= n == count;
  890.   }
  891.   if (!v) error("invariant failure");
  892.   return v;
  893. }
  894.